'''
Company: TWL
Author: xue jian
Email: xuejian@kanzhun.com
Date: 2020-09-08 13:53:39
'''
'''
n个海盗m个金币，现由第一个海盗计划分配方案，如果方案得到超过一半（包括自己）的支持，那么方案通过，就如此分配。
否则，这个海盗将被群体扔下海，再由剩下的人设计分配方案，一次类推。假设每个海盗足够理性，而且会尽量多得金币
（如果得到的金币数量相同，海盗更倾向于杀死同伴，多么凶残）。那么第一个人该如何分配金币？
由少推多。
'''
import heapq
class Solution:
    def GetCoins(self, n, m): #n 为人数，m为金币数，满足n<m
        re = [0]*n
        if n<=2: #（两个人的情况好想）
            re[0]=m
        else:
            re[2] = m
            for i in range(3, n): #i个人的时候，只需要知道i-1个人的最好分配方案，然后将金币最少的（i//2）个人的金币数量都加一
                                    #即可，这样能获得他们的支持。剩下的金币i个人都要了，这就是对他来说最好的分配方案。
                                    #所以还是个动态规划题。
                tmp = []
                for j in range(i):
                    tmp.append((re[j], j))
                add = heapq.nsmallest((i+1)//2, tmp)
                # print(add)
                tmp = [ii for _,ii in add]
                for j in range(i):
                    if j in tmp:
                        re[j]+=1
                    else:
                        re[j] = 0
                re[i] = m-sum(re[:i])
        return re

if __name__ == "__main__":
    solution = Solution()
    re = solution.GetCoins(5, 100)
    print([re[i] for i in range(len(re)-1, -1, -1)])